package exp8;

import java.util.*;

public class Dij {
    static int idx = 0;
    static HashMap<String, Integer> map = new HashMap<>();
    static String[] map2 = new String[100000];
    static class Node implements Comparable<Node> {
        int num;
        int d;

        Node(int a, int b) {
            num = a;
            d = b;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.d, other.d);
        }
    }

    static int s2i (String s) {
        if (map.containsKey(s)) {
            return map.get(s);
        } else {
            idx++;
            map.put(s, idx);
            map2[idx] = s;
            return idx;
        }
    }

    static String i2s (int n) {
        return map2[n];
    }

    static class Edge {
        int to;
        int w;

        Edge(int a, int b) {
            to = a;
            w = b;
        }
    }

    static final int INF = 0x3f3f3f3f;
    static final int MAXN = 1010;
    static List<Edge>[] G = new ArrayList[MAXN];
    static int[] d = new int[MAXN];
    static int[] parent = new int[MAXN];
    static boolean[] vis = new boolean[MAXN];

    static void djs(int s) {
        Arrays.fill(d, INF);
        Arrays.fill(parent, -1);
        Arrays.fill(vis, false);
        d[s] = 0;
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(s, d[s]));

        while (!q.isEmpty()) {
            int u = q.poll().num;

            if (vis[u]) {
                continue;
            } else {
                vis[u] = true;
            }

            for (Edge edge : G[u]) {
                int v = edge.to, w = edge.w;
                if (!vis[v] && d[v] > d[u] + w) {
                    d[v] = d[u] + w;
                    parent[v] = u;
                    q.add(new Node(v, d[v]));
                }
            }
        }
    }

    static void printPath(int end) {
        if (parent[end] == -1) {
            System.out.print(i2s(end));
            return;
        }
        printPath(parent[end]);
        System.out.print("->" + i2s(end));
    }

    public static void main(String[] args) {
        for (int i = 0; i < MAXN; i++) {
            G[i] = new ArrayList<>();
        }

        int n = 6;

        G[s2i("A")].add(new Edge(s2i("D"), 30));
        G[s2i("A")].add(new Edge(s2i("C"), 5));
        G[s2i("B")].add(new Edge(s2i("A"), 2));
        G[s2i("B")].add(new Edge(s2i("E"), 8));
        G[s2i("C")].add(new Edge(s2i("B"), 15));
        G[s2i("C")].add(new Edge(s2i("F"), 7));
        G[s2i("E")].add(new Edge(s2i("D"), 4));
        G[s2i("F")].add(new Edge(s2i("E"), 18));
        G[s2i("F")].add(new Edge(s2i("E"), 10));

        djs(1);

        if (d[n] < INF) {
            System.out.println("Shortest Distance: " + d[n]);
            System.out.print("Shortest Path: ");
            printPath(n);
        } else {
            System.out.println("No path found.");
        }
    }
}